%0 Conference Proceedings
%4 sid.inpe.br/mtc-m18/2013/12.10.18.24
%2 sid.inpe.br/mtc-m18/2013/12.10.18.24.26
%@issn 2179-4820
%T A parallel sweep line algorithm for visibility computation
%D 2013
%A Ferreira, Chaulio R.,
%A Andrade, Marcus V. A.,
%A Magalhaes, Salles V. G.,
%A Franklin, W. R.,
%A Pena, Guilherme C.,
%@affiliation Universidade Federal de Viçosa (UFV)
%@affiliation Universidade Federal de Viçosa (UFV)
%@affiliation Universidade Federal de Viçosa (UFV)
%@affiliation Rensselaer Polytechnic Institute
%@affiliation Universidade Federal de Viçosa (UFV)
%E Andrade, Pedro Ribeiro,
%E Santanchè, André,
%B Simpósio Brasileiro de Geoinformática, 14 (GEOINFO).
%C Campos do Jordão
%8 24-27 nov. 2013
%I Instituto Nacional de Pesquisas Espaciais (INPE)
%J São José dos Campos
%P 12
%S Anais
%X This paper describes a new parallel raster terrain visibility (or viewshed) algorithm, based on the sweep-line model of [Van Kreveld 1996]. Computing the terrain visible from a given observer is required for many GIS applications, with applications ranging from radio tower siting to aesthetics. Processing the newly available higher resolution terrain data requires faster architectures and algorithms. Since the main improvements on modern processors come from multi-core architectures, parallel programming provides a promising means for developing faster algorithms. Our algorithm uses the economical and widely available shared memory model with OpenMP. Experimentally, our parallel speedup is almost linear. On 16 parallel processors, our algorithm is up to 12 times faster than the serial implementation.
%@language en
%3 paper9.pdf